/**
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 * 最长回文子串
 * @param s 
 */
const longestPalindrome = (s: string): string => {

    // dp[i, j] 表示i~j内的最长回文子串
    const len = s.length;
    // 默认都是1
    const dp: number[] = new Array(len).fill(0)

    let ans = s[0]
    for (let i = len - 1; i >= 0; i--) {
        // 默认每一项都是1
        dp[i] = 1

        let cur = 0
        // 处理i后面的
        for (let j = i + 1; j < len; j++) {
            let leftBottom = cur;

            // 保存当前的最大长度, 下一次循环当作leftBottom
            cur = dp[j]

            if (s[i] === s[j]) {
                let curLen = 1
                // 中间也是回文子串, 就更新, 否则就是1
                if (j - i === 1) {
                    // 两个并列在一起的
                    curLen = 2
                } else if (j - i - 1 === leftBottom) {
                    // 不是并列在一起的
                    // (i, j)是回文子串, 不包括i和j
                    curLen = leftBottom + 2

                }
                // 比较长度, 获取最大的字符串
                ans = curLen > ans.length ? s.substring(i, i + curLen) : ans

                // 保存当前的最大长度
                dp[j] = curLen;
            } else {
                dp[j] = 1
            }
        }
    }

    return ans
};